//题解链接🔗 https://leetcode.cn/problems/Qv1Da2/solutions/2246093/c-chao-xiang-xi-zhu-shi-zhan-die-dai-fei-nidw/?orderBy=newest_to_oldest
#include <iostream>
#include <stack>
using namespace std;
// Definition for a Node.
class Node
{
public:
    int val;
    Node *prev;
    Node *next;
    Node *child;
};
// 递归
class Solution
{
public:
    Node *__flatten(Node *prev, Node *head)
    {
        //[递归]针对每一个节点都这样操作
        // 如果head为空返回上一个节点这样最后返回的就是最后一个节点
        if (!head)
            return prev;
        // 将当前节点拼接到上一个节点
        if (prev)
        {
            prev->next = head;
            head->prev = prev;
            prev->child = nullptr;
        }
        // 提前保存下一个节点(拼接完底层节点后head->next会改变)
        Node *next = head->next;
        // 先拼接所有底层节点再拼接剩余的同层节点
        return __flatten(__flatten(head, head->child), next);
    }
    Node *flatten(Node *head)
    {
        Node *ret = head;
        __flatten(nullptr, head);
        return ret;
    }
};
// 栈迭代
class Solution
{
public:
    Node *flatten(Node *head)
    {
        if (!head)
            return head;
        // 用栈保存上层节点
        stack<Node *> st;
        Node *pev = head;
        // 初始化迭代器
        st.push(pev->next);
        if (pev->child)
            st.push(pev->child);
        // 迭代器
        while (!st.empty())
        {
            Node *cur = st.top();
            st.pop();
            // 优先向下遍历
            while (cur)
            {
                // 拼接到上一个节点
                pev->next = cur;
                cur->prev = pev;
                pev->child = nullptr;
                pev = cur;
                if (cur->child)
                {
                    // 如果有底层节点就把当前层下一个节点入栈
                    st.push(cur->next);
                    cur = cur->child;
                }
                else
                {
                    cur = cur->next;
                }
            }
        }
        return head;
    }
};